import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
    List<String> ret;
    StringBuilder build;
    public List<String> letterCasePermutation(String s) {
        char[] ss=s.toCharArray();
        int n=ss.length;
        ret=new ArrayList<>();
        build=new StringBuilder();

        backtrack(ss,0);
        StringBuilder q=new StringBuilder("....");




        return ret;

    }

    public static void main(String[] args) {

        char[] d={'.','.','.','.'};

        System.out.println(d.toString());
    }

    private void backtrack(char[] s,int pos){
        int n=s.length;

        if(n==pos){
            ret.add(build.toString());
            return;
        }

        if(Character.isLetter(s[pos])){
            build.append(s[pos]);
            backtrack(s,pos+1);
            build.deleteCharAt(build.length()-1);

            char c=(char)(s[pos]-32);

            if(!Character.isLetter(c)) c=(char)(s[pos]+32);
            build.append(c);
            backtrack(s,pos+1);
            build.deleteCharAt(build.length()-1);

        }else{
            build.append(s[pos]);
            backtrack(s,pos+1);
            build.deleteCharAt(build.length()-1);

        }



    }
}

class Solution1 {
    int ret=0;
    boolean[] vis;
    public int countArrangement(int n) {

        vis=new boolean[n+1];
        backtrack(n,1);
        return ret;
    }

    private void backtrack(int n,int pos){

        if(pos>n){
            ret++;
            return;
        }

        for(int i=1;i<=n;i++){
            if(vis[i]||i%pos!=0&&pos%i!=0) continue;
            vis[i]=true;
            backtrack(n,pos+1);
            vis[i]=false;
        }

    }

    
}


//回溯的方式解决数独
class Solution2 {
    boolean[][] rowVisited;  // 记录每行的数字是否已使用
    boolean[][] colVisited;  // 记录每列的数字是否已使用
    boolean[][][] boxVisited; // 记录每个 3x3 宫的数字是否已使用

    public boolean isValidSudoku(char[][] board) {
        rowVisited = new boolean[9][10];  // 9行，数字1-9
        colVisited = new boolean[9][10];  // 9列，数字1-9
        boxVisited = new boolean[3][3][10]; // 3x3宫，数字1-9

        return backtrack(board, 0);  // 从第0行开始检查
    }

    private boolean backtrack(char[][] board, int row) {
        if (row == 9) {
            return true;  // 所有行都检查完毕，数独有效
        }

        for (int col = 0; col < 9; col++) {
            char c = board[row][col];
            if (c == '.') {
                continue;  // 空格跳过
            }

            int num = c - '0';
            int boxRow = row / 3;
            int boxCol = col / 3;

            // 检查当前数字是否已在行、列或宫中出现
            if (rowVisited[row][num] || colVisited[col][num] || boxVisited[boxRow][boxCol][num]) {
                return false;  // 冲突，直接返回false
            }

            // 标记当前数字已使用
            rowVisited[row][num] = true;
            colVisited[col][num] = true;
            boxVisited[boxRow][boxCol][num] = true;
        }

        // 递归检查下一行
        boolean isValid = backtrack(board, row + 1);

        // 回溯：撤销当前行的标记（虽然验证问题不需要回溯，但为了结构完整）,回不回溯都可以通过
        for (int col = 0; col < 9; col++) {
            char c = board[row][col];
            if (c == '.') {
                continue;
            }
            int num = c - '0';
            int boxRow = row / 3;
            int boxCol = col / 3;

            rowVisited[row][num] = false;
            colVisited[col][num] = false;
            boxVisited[boxRow][boxCol][num] = false;
        }

        return isValid;
    }
}


//直接遍历的方式，验证数独是否有效
class Solution3 {
    boolean[][] rowVis;   // 记录每行的数字是否使用过
    boolean[][] colVis;   // 记录每列的数字是否使用过
    boolean[][][] boxVis; // 记录每个3x3宫的数字是否使用过

    public boolean isValidSudoku(char[][] board) {
        rowVis = new boolean[9][10];  // 9行，数字1-9
        colVis = new boolean[9][10];  // 9列，数字1-9
        boxVis = new boolean[3][3][10]; // 3x3宫，数字1-9

        // 首先检查初始棋盘是否有效
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    // 检查行、列和3x3宫是否已经有这个数字
                    if (rowVis[i][num] || colVis[j][num] || boxVis[i/3][j/3][num]) {
                        return false;
                    }
                    // 标记数字已使用
                    rowVis[i][num] = true;
                    colVis[j][num] = true;
                    boxVis[i/3][j/3][num] = true;
                }
            }
        }
        return true;
    }
}



class Solution5 {
    boolean[][] colUsed;    // 记录每列数字是否使用
    boolean[][] rowUsed;    // 记录每行数字是否使用
    boolean[][][] boxUsed;  // 记录每个3×3宫格数字是否使用

    public void solveSudoku(char[][] board) {
        colUsed = new boolean[9][10];  // 数字1~9，索引1~9
        rowUsed = new boolean[9][10];
        boxUsed = new boolean[3][3][10];

        // 初始化已存在的数字
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    rowUsed[i][num] = true;
                    colUsed[j][num] = true;
                    boxUsed[i / 3][j / 3][num] = true;
                }
            }
        }

        backtrack(board, 0, 0);  // 从(0,0)开始填
    }

    private boolean backtrack(char[][] board, int row, int col) {
        if (row == 9) {
            return true;  // 填完所有行，成功
        }

        if (col == 9) {
            return backtrack(board, row + 1, 0);  // 换到下一行
        }

        if (board[row][col] != '.') {
            return backtrack(board, row, col + 1);  // 已有数字，跳过
        }

        // 尝试填入1~9
        for (int num = 1; num <= 9; num++) {
            if (!rowUsed[row][num] && !colUsed[col][num] && !boxUsed[row / 3][col / 3][num]) {
                board[row][col] = (char) (num + '0');
                rowUsed[row][num] = true;
                colUsed[col][num] = true;
                boxUsed[row / 3][col / 3][num] = true;

                if (backtrack(board, row, col + 1)) {
                    return true;  // 递归成功，直接返回
                }

                // 回溯，撤销选择
                board[row][col] = '.';
                rowUsed[row][num] = false;
                colUsed[col][num] = false;
                boxUsed[row / 3][col / 3][num] = false;
            }
        }

        return false;  // 当前格子无法填入任何数字，回溯
    }
}